GermanWikipedia - /page/entry.mu

Micron Document

<!DOCTYPE html>

<title>Golomb-Lineal</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Golomb-Lineal</h1>

</header>

</div>

Ein Golomb-Lineal oder Golomb-Maßstab (häufig auch <a href="Englische_Sprache" title="Englische Sprache">englisch</a> Golomb Ruler nach dem englischen Fachbegriff) ist in der <a href="Zahlentheorie" title="Zahlentheorie">Zahlentheorie</a> ein <a href="Lineal" title="Lineal">Lineal</a> mit Markierungen an <a href="Ganze_Zahl" title="Ganze Zahl">ganzzahligen</a> Positionen, bei dem es keine zwei Paare von Markierungen mit dem gleichen Abstand zueinander gibt. Golomb-Lineale haben ihren Namen von <a href="Solomon_W._Golomb" title="Solomon W. Golomb">Solomon W. Golomb</a>, einem US-amerikanischen Professor für Mathematik und Elektrotechnik an der <a href="University_of_Southern_California" title="University of Southern California">Universität von Südkalifornien</a>.

Ein Golomb-Lineal kann definiert werden als <a href="Endliche_Menge" title="Endliche Menge">endliche Menge</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M\subset \mathbb {Z} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M\subset \mathbb {Z} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ac14eb4dd7772c1ca6fd575305cd3eb9bba64aab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.091ex; height:2.176ex;" alt="{\displaystyle M\subset \mathbb {Z} }" loading="lazy"> mit der Eigenschaft: wenn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a,b,c,d\in M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a,b,c,d\in M}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/503ca6d63e220c2631a51ad29fd198a62bdb1d0a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.835ex; height:2.509ex;" alt="{\displaystyle a,b,c,d\in M}" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\neq b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\neq b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3bf17ce351d08f2b7a3e54ba3aa2132f260c84f6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.326ex; height:2.676ex;" alt="{\displaystyle a\neq b}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |a-b|=|c-d|}">

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |a-b|=|c-d|}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fcefde5528625a14d0cb5d603e0a236635fc37b6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.817ex; height:2.843ex;" alt="{\displaystyle |a-b|=|c-d|}" loading="lazy">, dann ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{a,b\}=\{c,d\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{a,b\}=\{c,d\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8830b503a10c29c1e4a83db1f061b6fc01a7b4a0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.266ex; height:2.843ex;" alt="{\displaystyle \{a,b\}=\{c,d\}}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Allgemeines">Allgemeines</h2></div>

Golomb-Lineale werden anhand ihrer Ordnung und ihrer Länge kategorisiert. Die Ordnung eines Golomb-Lineals ist dabei definiert durch die Anzahl der Markierungen, die Länge durch den größten Abstand zweier Markierungen. Da <a href="Parallelverschiebung" title="Parallelverschiebung">Parallelverschiebung</a> und <a href="Spiegelung_(Geometrie)" title="Spiegelung (Geometrie)">Spiegelung</a> bei Golomb-Linealen als triviale Operationen angesehen werden, wird die erste Markierung üblicherweise bei 0 gesetzt und diejenige, die den kleinsten Abstand von einer Endmarkierung hat, an der kleineren der beiden möglichen positiven Positionen (sodass die erste und die zweite näher beieinander sind als die vorletzte und die letzte Markierung). Außerdem sollen die Abstände keinen gemeinsamen Teiler haben, sonst könnte man das Lineal um diesen Faktor verkürzen ([0,2,8,12] → [0,1,4,6]).

Ein Golomb-Lineal muss nicht alle Abstände bis zu seiner Länge messen können, es müssen also nicht alle Abstände zwischen den Markierungen – aufsteigend geordnet – eine lückenlose Zahlenreihe (1,2,3,4,5,…) ergeben. Wenn das jedoch der Fall ist, wird es ein perfektes Golomb-Lineal genannt. Es existieren keine perfekten Golomb-Lineale mit einer Ordnung größer als vier.<a href="#cite_note-mcgill.ca-1">[1]</a> Ein Golomb-Lineal ist optimal, wenn es keine kürzeren Lineale derselben Ordnung gibt. Optimale Golomb-Lineale für eine gegebene Ordnung zu finden ist, im Gegensatz zum Erstellen von Linealen mit Golomb-Eigenschaft, eine rechenintensive Aufgabe. Mittels <a href="Verteiltes_Rechnen" class="mw-redirect" title="Verteiltes Rechnen">verteilten Rechnens</a> wurden bislang optimale Golomb-Lineale bis zur Ordnung 28 durch das <a href="Distributed.net" title="Distributed.net">distributed.net</a>-Projekt bestätigt. Das Projekt bestätigte zuletzt nach einer Gesamtdauer von über 8 Jahren das bis dahin kürzeste bekannte Lineal für die Ordnung 28.<a href="#cite_note-Completion_of_OGR-28_project-2">[2]</a>

Die Suche nach einem optimalen Lineal der Ordnung 29 ist mit Stand 2022 von <a href="Distributed.net" title="Distributed.net">distributed.net</a> nicht geplant, da der Aufwand zu hoch erscheint.<a href="#cite_note-Completion_of_OGR-28_project-2">[2]</a>

<div class="mw-heading mw-heading2"><h2 id="Anwendung">Anwendung</h2></div>

Golomb-Lineale finden Anwendung beim Entwurf von <a href="Phased-Array-Antenne" title="Phased-Array-Antenne">Gruppenantennen</a> wie beispielsweise <a href="Radioteleskop" title="Radioteleskop">Radioteleskopen</a>. Antennen in [0,1,4,6] Golomb-Anordnung findet man häufig bei <a href="Mobilfunk" title="Mobilfunk">Mobilfunkmasten</a>. Auch die Anordnung von Feldsensoren in Kernspintomographie nutzt Eigenschaften von Golomb-Maßstäben.

Bei beiden Anwendungen ist das Ziel, mit einer Minimalzahl an Elementen (Antennen, Sensoren) eine Maximalzahl an unterschiedlichen Abständen und im Dreidimensionalen eine Maximalzahl an verschiedenen Abstrahl- und Empfangswinkeln zu erreichen. Sind die verwendeten Golomb-Lineale optimal, wird auch noch die Ausdehnung des Messsystems bzw. der Gruppenantenne minimiert, was die Handhabbarkeit verbessert oder einen Einsatz überhaupt erst ermöglicht.

<div class="mw-heading mw-heading2"><h2 id="Bekannte_optimale_Golomb-Lineale">Bekannte optimale Golomb-Lineale</h2></div>

Die Tabelle zeigt die Werte für alle derzeit bekannten optimalen Golomb-Lineale bis zur Ordnung 28, wobei äquivalente Lineale (das heißt in umgekehrter Reihenfolge zu einem der angegebenen) nicht enthalten sind. Die ersten Vier stellen dabei perfekte Golomb-Lineale dar.

<th>Ordnung</th>

<th>Länge</th>

<th>Markierungen</th>

<th>Bewiesen am</th>

<th>Bewiesen durch

</th></tr>

<tr>

<td>Wallace Babcock

</td></tr>

<tr>

<td>Wallace Babcock

</td></tr>

<tr>

<td>Wallace Babcock

</td></tr>

<tr>

<td>Wallace Babcock

</td></tr>

<tr>

<td>John P. Robinson and Arthur J. Bernstein

</td></tr>

<tr>

<td>John P. Robinson and Arthur J. Bernstein

</td></tr>

<tr>

<td>John P. Robinson and Arthur J. Bernstein

</td></tr>

<tr>

<td>William Mixon

</td></tr>

<tr>

<td>William Mixon

</td></tr>

<tr>

<td>William Mixon

</td></tr>

<tr>

<td>William Mixon

</td></tr>

<tr>

<td>John P. Robinson

</td></tr>

<tr>

<td>John P. Robinson

</td></tr>

<tr>

<td>James B. Shearer

</td></tr>

<tr>

<td>James B. Shearer

</td></tr>

<tr>

<td>James B. Shearer

</td></tr>

<tr>

<td>W. Olin Sibert

</td></tr>

<tr>

<td>W. Olin Sibert

</td></tr>

<tr>

<td>Apostolos Dollas, William T. Rankin and David McCracken

</td></tr>

<tr>

<td>Mark Garry, David Vanderschel et al. (web project)

</td></tr>

<tr>

<td>Mark Garry, David Vanderschel et al. (web project)

</td></tr>

<tr>

<td>Mark Garry, David Vanderschel et al. (web project)

</td></tr>

<tr>

<td>Mark Garry, David Vanderschel et al. (web project)

</td></tr>

<tr>

<td>13. Oktober 2004<a href="#cite_note-distributed.net_OGR-24_completion_announcement-7">[7]</a></td>